package Demo;

import java.util.HashSet;
import java.util.List;

public class Demo3 {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> hash=new HashSet(wordDict);
        int n=s.length();
        s=" "+s;
        boolean []dp=new boolean[n+1];
        dp[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=i;j>=1;j--){
                if(dp[j-1]&&hash.contains(s.substring(j,i+1))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }


    public int findSubstringInWraproundString(String ss) {
        char []s=ss.toCharArray();
        int n=ss.length();
        int []dp=new int[n];
        for(int i=0;i<n;i++)dp[i]=1;

        for(int i=1;i<n;i++){
            if(s[i-1]+1==s[i]||s[i-1]=='z'&&s[i]=='a'){
                dp[i]+=dp[i-1];
            }
        }
        int []arr=new int[26];
        for(int i=0;i<n;i++){
            arr[s[i]-'a']=Math.max(arr[s[i]-'a'],dp[i]);
        }
        int sum=0;
        for(int i=0;i<26;i++)sum+=arr[i];
        return sum;
    }

    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int []dp=new int [n];
        for(int i=0;i<n;i++){
            dp[i]=1;
        }
        int ret=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
            }
            ret=Math.max(dp[i],ret);
        }
        return ret;
    }

}
